package com.lsa.letcode.the21.mergeSortedLists;

import com.lsa.letcode.common.ListNode;

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    	if (isEmpty(l1)) {
    		return l2;
    	}
    	else if (isEmpty(l2)) {
    		return l1;
    	}
    	
    	ListNode[] headPtr = new ListNode[1];
    	ListNode front = null;
    	
    	while(l1 != null || l2 != null) {
    		if (l1 != null && l2 != null) {
    			int cmp = compare(l1, l2);
    			if (cmp <= 0) {
    				front = append(front, l1, headPtr);
    				l1 = l1.next;
    			}
    			if (cmp >= 0) {
    				front = append(front, l2, headPtr);
    				l2 = l2.next;
    			}
    		}
    		else if (l1 != null){
    			front = append(front, l1, headPtr);
				break;
    			
    		}
    		else { // l2 != null
    			front = append(front, l2, headPtr);
    			break;
    		}
    	}
    	
        return headPtr[0];
    }
    
    private int compare(ListNode l1, ListNode l2) {
    	return l1.val - l2.val;
    }
    
    private ListNode append(ListNode front, ListNode l, ListNode[] head) {
    	if (front == null) {
    		front = l;
    		head[0] = front;
    	}
    	else {
    		front.next = l;
    		front = front.next;
    	}
    	return front;
    }
    
    private boolean isEmpty(ListNode l1) {
    	return l1 == null;
    }
}